package com.zhengb.algorithmdemo.basic.queue;

import com.zhengb.algorithmdemo.basic.stack.LLNode;
import com.zhengb.algorithmdemo.basic.stack.LinkListBaseStack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 链表为基础实现的队列
 * front->node1->node2->node3->rear
 *
 * @author zhengbo
 * @date 2020/2/19
 */
public class LinkListBaseQueue<T> {

    private LLNode<T> frontNode;

    private LLNode<T> rearNode;

    private LinkListBaseQueue() {
        this.frontNode = null;
        this.rearNode = null;
    }

    public static <T> LinkListBaseQueue<T> createQueue() {
        return new LinkListBaseQueue<>();
    }

    public boolean isEmpty() {
        return frontNode == null;
    }

    /**
     * 加入队列
     *
     * @param data
     */
    public void enQueue(T data) {

        LLNode<T> newNode = new LLNode<>(data);
        if (rearNode != null) {
            rearNode.setNextNode(newNode);
        }

        rearNode = newNode;
        if (frontNode == null) {
            frontNode = rearNode;
        }
    }

    /**
     * 出队列
     *
     * @return
     */
    public T deQueue() {

        T data;

        if (isEmpty()) {
            return null;
        } else {
            data = frontNode.getData();
            frontNode = frontNode.getNextNode();
        }

        return data;
    }

    /**
     * 按顺序获取队列数据
     * 利用栈对数据反转
     *
     * @return
     */
    public List<T> getQueueDataFromRear() {

        if (isEmpty()) {
            return Collections.emptyList();
        }

        LinkListBaseStack<T> stack = new LinkListBaseStack<>();

        LLNode<T> curNode = frontNode;

        stack.push(curNode.getData());

        while ((curNode = curNode.getNextNode()) != null) {
            stack.push(curNode.getData());
        }

        return stack.getStackList();
    }

    public List<T> getQueueDataFromFront() {

        if (isEmpty()) {
            return Collections.emptyList();
        }
        List<T> resultList = new ArrayList<>();

        LLNode<T> curNode = frontNode;
        resultList.add(curNode.getData());

        while ((curNode = curNode.getNextNode()) != null) {
            resultList.add(curNode.getData());
        }

        return resultList;
    }

    public void deleteQueue() {

        for (LLNode<T> x = frontNode; x != null; ) {
            LLNode<T> next = x.getNextNode();
            x.setData(null);
            x.setNextNode(null);
            x = next;
        }
    }

    public static void main(String[] args) {


        LinkListBaseQueue<Integer> queue = LinkListBaseQueue.createQueue();

        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);

        System.out.println(queue.getQueueDataFromFront());
        System.out.println(queue.getQueueDataFromRear());

        queue.deleteQueue();

        System.out.println("...");
    }

}
